# 作者: YYJ
# 2025年06月24日15时21分31秒
# 2486249622@qq.com

import random
import time


class Sort:
    def __init__(self, arr_num, num_range):
        self.arr = []
        self.arr_num = arr_num  # 数组长度
        self.num_range = num_range  # 数字范围
        self.__create_random_num()
        self.tmp_arr = [0] * self.arr_num

    def __create_random_num(self):
        """
        实现随机数
        :return:
        """
        for i in range(self.arr_num):
            self.arr.append(random.randint(0, self.num_range - 1))  # randint左闭右闭

    def __adjust_max_heap__(self, adjust_pos, length):
        """
        调整最大堆
        :param adjust_pos:
        :param length:
        :return:
        """
        dad = adjust_pos
        son = 2 * dad + 1  # 左孩子
        while son < length:
            if son + 1 < length and self.arr[son] < self.arr[son + 1]:
                son += 1
            if self.arr[dad] < self.arr[son]:
                self.arr[dad], self.arr[son] = self.arr[son], self.arr[dad]
                dad = son
                son = 2 * dad + 1
            else:
                break

    def heap_sort(self):
        """
        堆排序
        :return:
        """
        l = self.arr_num
        for dad_pos in range(l // 2 - 1, - 1, -1):
            self.__adjust_max_heap__(dad_pos, l)
        self.arr[0], self.arr[self.arr_num - 1] = self.arr[self.arr_num - 1], self.arr[0]
        for i in range(self.arr_num - 1, 0, -1):
            self.__adjust_max_heap__(0, i)  # 调整最大堆
            self.arr[0], self.arr[i - 1] = self.arr[i - 1], self.arr[0]  # 堆顶元素和当前元素交换位置

    def __merge__(self, low, mid, high):
        tmp = self.tmp_arr
        for i in range(low, high + 1):
            tmp[i] = self.arr[i]
        i = low
        j = mid + 1
        k = low
        while i <= mid and j <= high:
            if tmp[i] <= tmp[j]:
                self.arr[k] = tmp[i]
                k += 1
                i += 1
            else:
                self.arr[k] = tmp[j]
                k += 1
                j += 1

        while i <= mid:
            self.arr[k] = tmp[i]
            k += 1
            i += 1

        while j <= high:
            self.arr[k] = tmp[j]
            k += 1
            j += 1

    def merge_sort(self, low, high):
        if low < high:
            mid = (low + high) // 2
            self.merge_sort(low, mid)
            self.merge_sort(mid + 1, high)
            self.__merge__(low, mid, high)

    def cal_sort_time(self, sort_method, *args, **kwargs):
        start = time.time()
        sort_method(*args, **kwargs)
        end = time.time()
        print(f'排序耗时: {end - start}')

    def count_sort(self):
        count_arr = [0] * self.num_range  # 以数范围创建一个数组，用于记录每个数字出现的次数
        for i in self.arr:
            count_arr[i] += 1
        k = 0
        for i in range(self.num_range):
            for j in range(count_arr[i]):
                self.arr[k] = i
                k += 1


if __name__ == '__main__':
    s = Sort(1000000, 100)
    # print(s.arr)
    # s.heap_sort()
    # print(s.arr)
    # s.merge_sort(0, s.arr_num - 1)
    # print(s.arr)
    # s.cal_sort_time(s.heap_sort)
    # s.cal_sort_time(s.merge_sort, 0, s.arr_num - 1)
    s.cal_sort_time(s.count_sort)
    # print(s.arr)
